package com.agile.leetcode.hot.middle;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import static jodd.util.Wildcard.match;

/**
 * 查找和替换模式
 * 你有一个单词列表 words 和一个模式  pattern，你想知道 words 中的哪些单词与模式匹配。
 *
 * 如果存在字母的排列 p ，使得将模式中的每个字母 x 替换为 p(x) 之后，我们就得到了所需的单词，那么单词与模式是匹配的。
 *
 * （回想一下，字母的排列是从字母到字母的双射：每个字母映射到另一个字母，没有两个字母映射到同一个字母。）
 *
 * 返回 words 中与给定模式匹配的单词列表。
 *
 * 你可以按任何顺序返回答案。
 *
 *  
 *
 * 示例：
 *
 * 输入：words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
 * 输出：["mee","aqq"]
 * 解释：
 * "mee" 与模式匹配，因为存在排列 {a -> m, b -> e, ...}。
 * "ccc" 与模式不匹配，因为 {a -> c, b -> c, ...} 不是排列。
 * 因为 a 和 b 映射到同一个字母。
 *
 * @Author:ChenZhangKun
 * @Date: 2021/6/26 11:56
 */
public class FindAndReplacePattern {
    public static void main(String[] args) {
        FindAndReplacePattern replacePattern=new FindAndReplacePattern();
        String[] words = {"abc","deq","mee","aqq","dkd","ccc"};
        String pattern="abb";
        List<String> list = replacePattern.findAndReplacePattern(words, pattern);
        System.out.println(list);
    }
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> result = new ArrayList<>();
        for (String word : words) {
            if (match(word, pattern)) {
                result.add(word);
            }
        }
        return result;
    }

    private boolean match(String word, String pattern) {
        Map<Character, Character> map1 = new HashMap<>(16);
        Map<Character, Character> map2 = new HashMap<>(16);
        for (int i = 0; i < word.length(); i++) {
            char c1 = word.charAt(i);
            char c2 = pattern.charAt(i);
            if (!map1.containsKey(c1)) {
                map1.put(c1, c2);
            }
            if (!map2.containsKey(c2)) {
                map2.put(c2, c1);
            }
            if (map1.get(c1) != c2 || map2.get(c2) != c1) {
                return false;
            }
        }
        return true;
    }
}
class Practice_1{
    public static void main(String[] args) {
        Practice_1 replacePattern=new Practice_1();
        String[] words = {"abc","deq","mee","aqq","dkd","ccc"};
        String pattern="abb";
        List<String> list = replacePattern.findAndReplacePattern(words, pattern);
        System.out.println(list);
    }
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        // 遍历
        List<String > result=new ArrayList<>();
        for (String word : words) {
            if (match_1(word,pattern)){
                result.add(word);
            }
        }
        return result;
    }

    private boolean match_1(String word, String pattern) {
        // 创建map
        Map<Character,Character> map1=new HashMap<>();
        Map<Character,Character> map2=new HashMap<>();
        // 遍历
        for (int i = 0; i < word.length(); i++) {
            //
            char c1=word.charAt(i);
            char c2=pattern.charAt(i);
            // 加入map
            if (!map1.containsKey(c1)){
                map1.put(c1,c2);
            }
            if (!map2.containsKey(c2)){
                map2.put(c2,c1);
            }
            if (map1.get(c1)!=c2||map2.get(c2)!=c1){
                return false;
            }
        }
        return true;
    }
}
